package com.leetcode.solution.s7x;

public class SearchWord79 {
    public static void main(String[] args) {
        // ABCE
        // SFES
        // ADEE
        char[][] board = { { 'A', 'B', 'C', 'E' }, { 'S', 'F', 'E', 'S' }, { 'A', 'D', 'E', 'E' } };
        String word = "ABCESEEEFS";

        boolean result = new SearchWord79().exist(board, word);

        System.out.println(result);
    }
    public boolean exist(char[][] board, String word) {
        char fstCh = word.charAt(0);
        int maxRow = board.length;
        int maxCol = board[0].length;
        for (int row = 0; row < maxRow; row++) {
            for (int col = 0; col < maxCol; col++) {
                if (board[row][col] == fstCh) {
                    if (check(board, new boolean[maxRow][maxCol], word, row, col, 0)) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    private boolean check(char[][] board, boolean[][] visited, String word, int row, int col, int wordIdx) {
        if (board[row][col] != word.charAt(wordIdx)) {
            return false;
        } else if (wordIdx == word.length() - 1) {
            return true;
        }

        visited[row][col] = true;
        // 四个方向开始递归
        int[][] directions = new int[][] { {0, 1}, {0, -1}, {1, 0}, {-1, 0} };
        for (int[] direction : directions) {
            int newRow = row + direction[0];
            int newCol = col + direction[1];
            if (newRow >= 0 && newRow < board.length && newCol >= 0 && newCol < board[0].length && !visited[newRow][newCol]) {
                boolean subResult = check(board, visited, word, newRow, newCol, wordIdx + 1);
                if (subResult) {
                    return true;
                }
            }
        }

        visited[row][col] = false;

        return false;
    }
}
